'''
https://leetcode.cn/problems/k-inverse-pairs-array/description/
'''
from functools import cache


class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        MOD = 10**9 + 7
        def process(restN: int, restK: int) -> int:
            if restK == 0:
                return 1
            if restN < 0:
                return 0
            ways = 0
            for i in range(restN):
                # 0. 选择把他放在最后, 生成0 个逆序对
                # 1. 选择把他放在倒数第二, 生成1个逆序对
                # ...
                # restN-1. 选择把他放在最前边, 生成 restN - 1 个逆序对
                ways = (ways + process(restN - 1, restK - i)) % MOD
            return ways
        return process(n, k)

    def kInversePairs2(self, n: int, k: int) -> int:
        MOD = 10**9 + 7
        dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)]
        for restN in range(1, n + 1):
            dp[restN][0] = 1
            for restK in range(1, k + 1):
                ways = 0
                for i in range(min(restN, restK + 1)):
                    ways = (ways + dp[restN - 1][restK - i]) % MOD
                dp[restN][restK] = ways
        return dp[n][k]

    def kInversePairs3(self, n: int, k: int) -> int:
        MOD = 10**9 + 7
        dp = [[1] + [0] * k for _ in range(n + 1)]
        # 第一维度依赖前边的(一格)，第二维度依赖前边的(0 ~ min(i, j + 1))各
        # dp[i][j]
        # 依赖上一行 dp[i - 1][j - i]    i 属于[0, min(i, j+1)]
        # 所以其实当前依赖上一个格子，和左边格子(超过)即可，因为左边格子已经枚举了，上一行出了当前上方的所有左边的
        #           note 最远的上方的左边 j + 1个格子，所以如果超出，还需减掉这部分差值
        for i in range(1, n + 1):
            for j in range(1, k + 1):
                dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % MOD
                if j >= i:
                    dp[i][j] = (dp[i][j] - dp[i - 1][j-i] + MOD) % MOD
        return dp[n][k]